﻿using System;
using System.Text;

namespace exercise.队列
{
    //循环队列
    public class CircleQueue<E>
    {
        private int front;
        public int size { get; private set; }
        private E[] elements;
        private static readonly int DEFAULT_CAPACITY = 10;

        // 获取真实索引
        private int index(int index)
        {
            return (front + index) % elements.Length;
        }

        public CircleQueue()
        {
            //Queue<T>
            elements = new E[DEFAULT_CAPACITY];
        }

        public void enQueue(E element)
        {
            //自动扩容
            ensureCapacity(size + 1);

            elements[index(size)] = element;
            size++;
        }

        public E deQueue()
        {
            E frontElement = elements[front];
            elements[front] = default(E);
            front = index(1);
            size--;
            return frontElement;
        }

        public E getFront()
        {
            return elements[front];
        }

        public Boolean isEmpty()
        {
            return size == 0;
        }

        public void clear()
        {

            for (int i = 0; i < size; i++)
            {
                elements[index(i)] = default(E);
            }

            size = 0;
            front = 0;
        }

        /// <summary>
        /// 自动扩容
        /// </summary>
        /// <param name="capacity"></param>
        public void ensureCapacity(int capacity)
        {
            int oldCapacity = elements.Length;
            if (oldCapacity > capacity) return;

            //扩容1.5倍  >>1 相当于除以2
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            E[] newElements = new E[newCapacity];
            for (int i = 0; i < size; i++)
            {
                // 获取真实索引
                newElements[i] = elements[index(i)];
            }
            elements = newElements;

            front = 0; //已经是全新的数组了
            Console.WriteLine(oldCapacity + "扩容为" + newCapacity);
        }

        public override string ToString()
        {
            StringBuilder str = new StringBuilder();
            str.Append("capacity=").Append(elements.Length).Append("size=").Append(size).Append(", [");

            for (int i = 0; i < elements.Length; i++)
            {
                if (i != 0)
                {
                    str.Append(", ");
                }
                str.Append(elements[i]);
            }
            str.Append("]");

            return str.ToString();
        }
    }
}
